"""
给定一个无重复元素的数组 candidates和一个目标数target，
找出candidates中所有可以使数字和为target的组合。

candidates中的数字可以无限制重复被选取。

说明：

所有数字（包括target）都是正整数。
解集不能包含重复的组合。
"""

from typing import List


class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        n = len(candidates)
        if n == 0:
            return []
        path, result = [], []

        def dfs(candidates, begin, size, path, res, target):
            # 剪枝 + 回溯
            if target < 0:
                return
            if target == 0:
                res.append(path)
                return
            for idx in range(begin, size):
                dfs(candidates, idx, size, path+[candidates[idx]], res, target-candidates[idx])

        dfs(candidates, 0, n, path, result, target)
        return result


if __name__ == '__main__':
    t = [2, 3, 6, 7]
    s = Solution()
    print(s.combinationSum(t, 7))
